package com.wj.algorithm.lintcode;


public class P62 {
    private boolean sorted(int[] nums, int first, int last) {
        if(nums[last] > nums[first]) {
            return true;
        }
        return false;
    }
    public int search(int[] a, int target) {
        if(a == null || a.length <= 0) {
            return -1;
        }
        
        int len = a.length;
        if(len == 1) {
            return a[0] == target ? 0 : -1;
        }
        int left = 0;
        int right = len - 1;
        int mid = (left + right + 1) / 2;
        while(mid >= left && mid <= right) {
            int lv = a[left];
            int mv = a[mid];
            int rv = a[right];
            
            if(right - left <= 2) {
                for(int i = left; i <= right; i ++) {
                    if(a[i] == target) {
                        return i;
                    }
                }
                return -1;
            }
            
            boolean leftSorted = sorted(a, left, mid);
            if((leftSorted && target >= lv && target <= mv) || (!leftSorted && (target < mv || target > rv))) {//左边
                right = mid;
            } else {
                //右边
                left = mid;
            }
            mid = (left + right + 1) / 2;
        }
        
        return -1;
    }
    
    public static void main(String[] args) {
//        System.out.println(new P62().search(new int[]{1002,10203,9,10,100,101}, 9));
//        System.out.println(new P62().search(ArrayUtil.readIn(9), 8567));
    }
    
}
